package main

import "fmt"

func mergeSort(nums []int)[]int{
	if len(nums)<=1{
		return nums
	}
	m:=len(nums)/2
	a:=mergeSort(nums[:m])
	b:=mergeSort(nums[m:])
	return merge(a,b)
}

func merge(a []int,b []int)[]int{
	l1:=len(a)
	l2:=len(b)
	i,j:=0,0
	o:=[]int{}
	for i<l1 && j<l2 {
		if a[i]<b[j] {
			o = append(o,a[i])
			i++
		}else{
			o = append(o,b[j])
			j++
		}
	}
	
	o = append(o,a[i:]...)
	o = append(o,b[j:]...)
	return o
}

func main(){
	nums:=[]int{3,6,2,1,6,9}
	mergeSort(nums,0,len(nums)-1)
	fmt.Println(nums)
}